UVa/10065 - Useless tile packers/10065.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <algorithm>
   4 #include <iterator>
   5 #include <cmath>
   6
   7 using namespace std;
   8
   9
  10
  11 struct point{
  12   int x,y;
  13   point(int X, int Y) : x(X), y(Y) {}
  14 };
  15
  16 point pivot(10000, 10000);
  17
  18 ostream& operator<< (ostream& out, const point& c)
  19 {
  20   out << "(" << c.x << "," << c.y << ")";
  21   return out;
  22 }
  23
  24 double area(const vector<point> &p){
  25   double r = 0.0;
  26   for (int i=0; i<p.size(); ++i){
  27     int j = (i+1) % p.size();
  28     r += p[i].x*p[j].y - p[j].x*p[i].y;
  29   }
  30   return r/2.0;
  31 }
  32
  33 //retorna si c esta a la izquierda de el segmento AB
  34 int cross(const point &a, const point &b, const point &c){
  35   return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
  36 }
  37
  38 bool angleCmp(const point &self, const point &that){
  39   return( cross(pivot, that, self) < 0 );
  40 }
  41
  42 int distsqr(point a,  point b){
  43   return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
  44 }
  45
  46 //vector p tiene los puntos ordenados anticlockwise
  47 vector<point> graham(vector<point> p){
  48   pivot = p[0];
  49   sort(p.begin(), p.end(), angleCmp);
  50   for (int i=1; i<p.size()-1; ++i){
  51     if (cross(p[0], p[i], p[i+1]) == 0){
  52       if (distsqr(p[0], p[i]) < distsqr(p[0], p[i+1])){
  53         p.erase(p.begin() + i);
  54       }else{
  55         p.erase(p.begin() + i + 1);
  56       }
  57       i--;
  58     }
  59   }
  60
  61   /*cout << "Candidatos para el Convex Hull: " << endl;
  62   for (int i=0; i<p.size(); ++i) cout << p[i] << " ";
  63   cout << endl;*/
  64
  65   vector<point> chull(p.begin(), p.begin()+3);
  66
  67   //Ahora sí!!!
  68   for (int i=3; i<p.size(); ++i){
  69     while ( chull.size() >= 2 && cross(chull[chull.size()-2], chull[chull.size()-1], p[i]) < 0){
  70       chull.erase(chull.end() - 1);
  71     }
  72     chull.push_back(p[i]);
  73   }
  74
  75   /*  cout << "Nuestro Chull es: " << endl;
  76   for (int i=0; i<chull.size(); ++i) cout << chull[i] << " ";
  77   cout << endl;*/
  78
  79   return chull;
  80 }
  81
  82 int main(){
  83   int n;
  84   int tileNo = 1;
  85   while (cin >> n && n){
  86     vector<point> p;
  87     point min(10000, 10000);
  88     int minPos;
  89     for (int i=0; i<n; ++i){
  90       int x, y;
  91       cin >> x >> y;
  92       p.push_back(point(x,y));
  93       if (y < min.y || (y == min.y && x < min.x )){
  94         min = point(x,y);
  95         minPos = i;
  96       }
  97     }
  98
  99     /*cout << cross(p[0], p[1], p[2]) << endl;
 100       cout << "El punto " << p[2] << " esta a la " << (cross(p[0], p[1], p[2]) < 0 ? "derecha":"izquierda") << " del segmento " << p[0] << p[1] << endl;*/
 101
 102
 103     double tileArea = area(p);
 104     vector<point> sortedP;
 105
 106     if (tileArea > 0){
 107       for (int j=minPos,cuenta=1; cuenta<=p.size(); ++cuenta, j = (j+1)%p.size()){
 108         sortedP.push_back(p[j]);
 109       }
 110     }else{
 111       for (int j=minPos, cuenta=1; cuenta<=p.size(); ++cuenta, j = (j-1 < 0?j-1+p.size():j-1)){
 112         sortedP.push_back(p[j]);
 113       }
 114     }
 115     //cout << "Area es: " << area(p) << endl;
 116     /*for (int i=0; i<sortedP.size(); ++i) cout << sortedP[i] << " ";
 117       cout << endl;*/
 118     tileArea = fabs(tileArea);
 119     double chullArea = fabs(area(graham(sortedP)));
 120
 121     cout << "Tile #"<<tileNo++<<endl;
 122     printf("Wasted Space = %.2f \%\n\n",  (chullArea - tileArea) * 100.0 / chullArea);
 123
 124   }
 125   return 0;
 126 }